package 爆刷leetcode.balabala.三数之和;

import java.util.*;

/**
 * @Author yaya
 * @Create 2024/5/24 10:21
 * Description:
 */
public class Solution {
    // 三重循环
    public List<List<Integer>> threeSum(int[] nums) {

        // 超时啦
        Arrays.sort(nums);
        ArrayList<List<Integer>> list = new ArrayList<List<Integer>>();
        //     [-4,-1,-1,,0,1,2,]
        // 不取最后两个元素
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if ((nums[i] + nums[j] + nums[k]) == 0) {
                        list.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    }
                }
            }
        }

        // 使用set进行过滤重复数组
        HashSet<List<Integer>> set = new HashSet<List<Integer>>(list);
        list = new ArrayList<List<Integer>>(set);

        return list;
    }

    // 双指针
    public List<List<Integer>> threeSum2(int[] nums) {

        // 超时啦
        Arrays.sort(nums);
        ArrayList<List<Integer>> list = new ArrayList<List<Integer>>();

        int left;
        int right;
        //     [-4,-1,-1,0,1,2,]

        // 使用for循环锚定第一个数，然后后两个数使用双指针过滤
        for (int i = 0; i < nums.length; i++) {
            left = i + 1;
            right = nums.length - 1;
            // 如果是重复的数，则跳过
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            while (left < right) {
                // 如果是重复值
                if (left - 1 != i && left != 0 && nums[left] == nums[left - 1]) {
                    left++;
                    continue;
                }
                if (right != nums.length - 1 && nums[right] == nums[right + 1]) {
                    right--;
                    continue;
                }
                int result = nums[left] + nums[right] + nums[i];
                // 如果相加得0记录下来,然后元素往中间靠
                if (result == 0) {
                    list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                }

                // 小于0 则是left太小，要left++
                // 大于0，则是right太大，right--
                if (result < 0) {
                    left++;
                }
                if (result > 0) {
                    right--;
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // [-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]
        System.out.println(solution.threeSum2(new int[]{-1,0,1,2,-1,-4,-2,-3,3,0,4}));
    }


}
